package day2_linkedlist.mylink;

/**
 * 带虚拟头结点的单链表实现
 */
public class SingleLinkedListWithHead {
    // 虚拟头结点
    private Node dummyHead = new Node(-1);
    private int size;

    public void addFirst(int value) {
        addIndex(0,value);
    }

    public void addLast(int value) {
        addIndex(size,value);
    }

    public void addIndex(int index,int data) {
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        Node prev = dummyHead;
        // 此处需要多走一步，因为要多走一个虚拟头结点
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        // 此时prev就是待插入结点的前驱
        Node node = new Node(data);
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    public int getSize() {
        return size;
    }

    public void removeValueOnce(int value) {
        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == value) {
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size --;
                break;
            }
            prev = prev.next;
        }
    }

    public void removeAllValue(int value) {
        Node prev = dummyHead;
        while (prev.next != null) {
            // 删除完当前cur时，prev不能移动
            // 继续判断删除后的下个结点是否仍然是待删除的结点
            if (prev.next.val == value) {
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size --;
            }else {
                prev = prev.next;
            }
        }
    }

    @Override
    public String toString() {
        String ret = "";
        Node prev = dummyHead;
        while (prev.next != null) {
            ret += prev.next.val + "->";
            prev = prev.next;
        }
        ret += "NULL";
        return ret;
    }

    public static void main(String[] args) {
        SingleLinkedListWithHead singleLinkedListWithHead
                = new SingleLinkedListWithHead();
        singleLinkedListWithHead.addLast(1);
        singleLinkedListWithHead.addLast(3);
        singleLinkedListWithHead.addLast(7);
        singleLinkedListWithHead.addLast(7);
        singleLinkedListWithHead.addFirst(3);
        // 3-1-3-7-7
        System.out.println(singleLinkedListWithHead);
        singleLinkedListWithHead.removeAllValue(7);
        System.out.println(singleLinkedListWithHead);
    }
}
